Today's networks are formed of a number of network elements (NEs) interconnected by links (frequently optical fiber links). The links interconnecting the NEs may be arranged in one of a number of ways, resulting in various network topologies, such as ring, star, linear, and full-mesh topologies. It is also common for different autonomously managed subnetworks to be bridged to each other at various gateways, and for data transport services to be provided across the networks in a manner that is transparent to users.
Typically, data transport service provider networks serve client networks of limited geographic footprint, and the provider networks interconnect disparate client networks, generally providing longer haul data transport. In recent years for numerous reasons, including scalability, security, privacy, and simplicity of routing, provider networks have recognized value in presenting abstracted representations of their topologies to client NEs. For various reasons involving service level agreements and other contracts between managers of the data transport service providers and client networks, a current composition of the provider network, and numerous other factors, one of many possible abstracted network maps representing at least a few NEs of the provider network and a portion of the data transport capacity between the represented NEs, is created and disseminated to selected client network elements. Such an abstracted network map includes nodes representing corresponding NEs. Typically, only the NEs relevant to the client network are represented. For example, every edge provider NE (a NE of the provider network that is connected by a link to a client network NE) in the network may be represented. The abstracted network map may further include tandem network elements of the provider network, in order to reduce a number of links in the abstracted network map.
As noted, the reasons for presenting the abstracted view of the provider network include that many complicated details of allowable routes and network availability may be irrelevant to client NEs when determining routes, and to permit scalability of the provider network. The number of NEs represented in an abstracted network map is typically fewer than (and may be significantly fewer than) a number of NEs in the provider network. By presenting an abstracted network map with relatively few nodes and corresponding abstracted edges therebetween, searching and comparing available routes across the abstracted network maps becomes faster. In the foreseeable future there may be hundreds or thousands of PNEs in provider networks. The efficiency of using abstracted network maps is therefore becoming a necessity. Furthermore, only changes in network topology and connectivity that affect the NEs represented in the abstracted network map require changes in the corresponding abstracted network map. Other changes may require updating of metric information regarding abstracted links, but do not require changing the abstracted network map, which considerably facilitates changes in the configuration of the provider NEs.
Abstracted network maps may be associated with a route planning procedure that compensates for transmission level routing constraints such as those taught in co-pending co-assigned United States patent application entitled METHOD AND APPARATUS FOR DERIVING ALLOWABLE PATHS THROUGH A NETWORK WITH INTRANSITIVITY CONSTRAINTS filed Oct. 24, 2003 under Ser. No. 10/691,517, and United States patent application entitled METHOD AND APPARATUS FOR DERIVING OPTIMAL PATHS THROUGH A NETWORK SUBJECT TO A SUBSET SEQUENCE CONSTRAINT filed on Feb. 27, 2004 under Ser. No. 10/787,107. These and other route planning procedures (including some that are variations of Dijkstra's algorithm) require abstracted link metric information correctly associated with resource availability of the provider network, in order to correctly select optimal routes. However, no procedure for computing link metric information for abstracted network links (i.e. links in the abstract network map between NEs that may not be linked in the provider network, but rather represent a set of all available routes through the provider network between the represented NEs) is known.
Accordingly there remains a need for a method for computing metric information for abstracted links of an abstracted network map, the metric information corresponding to resource availability of an underlying network, so that the metric information can be used for route planning.